package com.qire.common.collect;

import java.util.Collection;
import java.util.Iterator;
import java.util.WeakHashMap;

import androidx.annotation.NonNull;

public class SafeIterableList<E>  implements Iterable<SafeIterableList.Node<E>> {
	
	@SuppressWarnings("WeakerAccess") /* synthetic access */
	Node<E> mStart;
    private Node<E> mEnd;
    
    // 使用WeakHashMap覆盖List<WeakReference>，因此我们不必手动删除其中包含null的WeakReference。
    private WeakHashMap<SupportRemove<E>, Boolean> mIterators = new WeakHashMap<>();
    private volatile int mSize = 0;

    /**
     * 判断索引是否在现有元素范围内
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < mSize;
    }
    
    /**
     * 返回指定元素索引处的节点，如果索引不在元素范围内则然会空。
     * @param index 索引
     * @return Node 元素节点
     */
    Node<E> node(int index) {
//    	assert isElementIndex(index);
    	
    	if(!isElementIndex(index)) {
    		return null;
    	}
    	
        if (index < (mSize >> 1)) {
            Node<E> x = mStart;
            for (int i = 0; i < index; i++)
                x = x.mNext;
            return x;
        } else {
            Node<E> x = mEnd;
            for (int i = mSize - 1; i > index; i--)
                x = x.mPrevious;
            return x;
        }
    }
    
    public Node<E> get(int index) {
        return node(index);
    }

    public Node<E> add(@NonNull E e) {
    	Node<E> newEntry = new Node<>(e);
        mSize++;
        if (mEnd == null) {
            mStart = newEntry;
            mEnd = mStart;
            return newEntry;
        }

        mEnd.mNext = newEntry;
        newEntry.mPrevious = mEnd;
        mEnd = newEntry;
        return newEntry;
    }

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        for (E e : (E[]) a) {
            add(e);
        }
        return true;
    }
	
	/**
     * 如果元素存在，则从该list中删除元素
     *
     * @param index 从list中删除指定索引位置的元素
     * @return 指定删除索引位置的元素,或者索引不在元素范围内 {@code null} 
     */
    public E remove(int index) {
    	Node<E> toRemove = node(index);
        if (toRemove == null) {
            return null;
        }
        mSize--;
        if (!mIterators.isEmpty()) {
            for (SupportRemove<E> iter : mIterators.keySet()) {
                iter.supportRemove(toRemove);
            }
        }

        if (toRemove.mPrevious != null) {
            toRemove.mPrevious.mNext = toRemove.mNext;
        } else {
            mStart = toRemove.mNext;
        }

        if (toRemove.mNext != null) {
            toRemove.mNext.mPrevious = toRemove.mPrevious;
        } else {
            mEnd = toRemove.mPrevious;
        }

        toRemove.mNext = null;
        toRemove.mPrevious = null;
        return toRemove.item;
    }

    /**
     * 从列表中删除所有元素。
     * 这个调用返回后，列表将为空。
     */
    public void clear() {
        for (Node<E> x = mStart; x != null; ) {
            Node<E> next = x.mNext;
//            x.item = null;
            x.mNext = null;
            x.mPrevious = null;
            x = next;
        }
        mStart = mEnd = null;
        mSize = 0;
    }

    /**
     * 如果列表中不包含元素，返回<tt>true</tt>。
     * @return 如果列表中不包含元素，返回<tt>true</tt>。
     */
    public boolean isEmpty() {
        return mSize == 0;
    }

    /**
     * @return 返回这个list的元素数量
     */
    public int size() {
        return mSize;
    }

	/**
     * @return 升序迭代器，它不包括迭代期间添加的新元素。
     */
    @NonNull
    @Override
    public Iterator<Node<E>> iterator() {
        ListIterator<E> iterator = new AscendingIterator<>(mStart, mEnd);
        mIterators.put(iterator, false);
        return iterator;
    }
	
	
	/**
     * @return 降序迭代器，它不包括迭代期间添加的新元素。
     */
    public Iterator<Node<E>> descendingIterator() {
        DescendingIterator<E> iterator = new DescendingIterator<>(mEnd, mStart);
        mIterators.put(iterator, false);
        return iterator;
    }
	
	/**
	 * @return 返回一个迭代器，它支持迭代期间增加元素
	 */
    public IteratorWithAdditions iteratorWithAdditions() {
        @SuppressWarnings("unchecked")
        IteratorWithAdditions iterator = new IteratorWithAdditions();
        mIterators.put(iterator, false);
        return iterator;
    }
    
	
    /**
     * @return 返回最早添加的项目或者null
     */
    public Node<E> eldest() {
        return mStart;
    }
    

    /**
     * @return 返回最新添加的项目或者null
     */
    public Node<E> newest() {
        return mEnd;
    }
	
	@Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof SafeIterableList)) {
            return false;
        }
        SafeIterableList list = (SafeIterableList) obj;
        if (this.size() != list.size()) {
            return false;
        }
        Iterator<Node<E>> iterator1 = iterator();
        Iterator iterator2 = list.iterator();
        while (iterator1.hasNext() && iterator2.hasNext()) {
        	Node<E> next1 = iterator1.next();
            Object next2 = iterator2.next();
            if ((next1 == null && next2 != null)
                    || (next1 != null && !next1.equals(next2))) {
                return false;
            }
        }
        return !iterator1.hasNext() && !iterator2.hasNext();
    }

    @Override
    public int hashCode() {
        int h = 0;
        Iterator<Node<E>> i = iterator();
        while (i.hasNext()) {
            h += i.next().hashCode();
        }
        return h;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        Iterator<Node<E>> iterator = iterator();
        while (iterator.hasNext()) {
            builder.append(iterator.next().toString());
            if (iterator.hasNext()) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }
	
	
	public static class Node<E> {
        final E item;
        Node<E> mNext;
        Node<E> mPrevious;
        
        Node(E element) {
        	if(null == element) {
        		throw new NullPointerException("Node element is null");
        	}
            this.item = element;
        }
        
        @Override
        public String toString() {
            return item.toString();
        }

        @SuppressWarnings("ReferenceEquality")
        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (!(obj instanceof Node)) {
                return false;
            }
            Node entry = (Node) obj;
            return item.equals(entry.item);
        }

        @Override
        public int hashCode() {
            return item.hashCode();
        }

        public E value() {
            return item;
        }
    }
	
	
    interface SupportRemove<E> {
        void supportRemove(@NonNull Node<E> entry);
    }
    
    private abstract static class ListIterator<E> implements Iterator<Node<E>>, SupportRemove<E> {
    	Node<E> mExpectedEnd;
    	Node<E> mNext;
		
		ListIterator(Node<E> start, Node<E> expectedEnd) {
		    this.mExpectedEnd = expectedEnd;
		    this.mNext = start;
		}
		
		@Override
		public boolean hasNext() {
		    return mNext != null;
		}
		
		@SuppressWarnings("ReferenceEquality")
		@Override
		public void supportRemove(@NonNull Node<E> entry) {
		    if (mExpectedEnd == entry && entry == mNext) {
		        mNext = null;
		        mExpectedEnd = null;
		    }
		
		    if (mExpectedEnd == entry) {
		        mExpectedEnd = backward(mExpectedEnd);
		    }
		
		    if (mNext == entry) {
		        mNext = nextNode();
		    }
		}
		
		@SuppressWarnings("ReferenceEquality")
        private Node<E> nextNode() {
		    if (mNext == mExpectedEnd || mExpectedEnd == null) {
		        return null;
		    }
		    return forward(mNext);
		}
		
		@Override
		public Node<E> next() {
			Node<E> result = mNext;
		    mNext = nextNode();
		    return result;
		}
		
		abstract Node<E> forward(Node<E> entry);
		
		abstract Node<E> backward(Node<E> entry);
	}

    /**
     * 升序迭代器
     * @param <E> 元素类型
     */
    static class AscendingIterator<E> extends ListIterator<E> {
        AscendingIterator(Node<E> start, Node<E> expectedEnd) {
            super(start, expectedEnd);
        }

        @Override
        Node<E> forward(Node<E> entry) {
            return entry.mNext;
        }

        @Override
        Node<E> backward(Node<E> entry) {
            return entry.mPrevious;
        }
    }

    /**
     * 降序迭代器
     * @param <E> 元素类型
     */
    private static class DescendingIterator<E> extends ListIterator<E> {

        DescendingIterator(Node<E> start, Node<E> expectedEnd) {
            super(start, expectedEnd);
        }

        @Override
        Node<E> forward(Node<E> entry) {
            return entry.mPrevious;
        }

        @Override
        Node<E> backward(Node<E> entry) {
            return entry.mNext;
        }
    }

    /**
     * 具有追加元素遍历的迭代器
     */
    private class IteratorWithAdditions implements Iterator<Node<E>>, SupportRemove<E> {
        private Node<E> mCurrent;
        private boolean mBeforeStart = true;

        IteratorWithAdditions() {
        }

        @SuppressWarnings("ReferenceEquality")
        @Override
        public void supportRemove(@NonNull Node<E> entry) {
            if (entry == mCurrent) {
                mCurrent = mCurrent.mPrevious;
                mBeforeStart = mCurrent == null;
            }
        }

        @Override
        public boolean hasNext() {
            if (mBeforeStart) {
                return mStart != null;
            }
            return mCurrent != null && mCurrent.mNext != null;
        }

        @Override
        public Node<E> next() {
            if (mBeforeStart) {
                mBeforeStart = false;
                mCurrent = mStart;
            } else {
                mCurrent = mCurrent != null ? mCurrent.mNext : null;
            }
            return mCurrent;
        }
    }
    
}
